부산대학교자료구조
Scientific Inference Lab

Up and Down One Level

Heap Update Operations

힙에 값을 넣으면 배열 끝에 붙인 뒤 sift up(새 값을 부모와 바꾸며 위로 올리기)으로, 최솟값을 빼면 마지막 값을 루트로 옮긴 뒤 sift down(루트 값을 더 작은 자식 노드와 바꾸며 내리기)으로 힙 성질을 되찾는다. 두 절차 모두 한 번에 한 레벨씩 움직이므로 교환은 많아야 높이만큼, 즉 O(log n)이다.

넣는 자리는 하나모양 조건을 지키려면 새 값은 마지막 레벨의 다음 빈 자리, 곧 배열의 끝에 붙인다.
sift up의 종료루트에 도달했거나 현재 값이 부모의 값 이상이면 멈춘다.
sift down의 교환 대상존재하는 자식 노드 가운데 더 작은 쪽과 바꾼다. 큰 쪽과 바꾸면 새 부모가 다른 자식 노드보다 커질 수 있다.
heapqheappush는 끝에 붙이고 sift up, heappop은 마지막 값을 올리고 sift down하는 절차다.

새 값은 배열 끝에 붙은 뒤 부모보다 작은 동안 한 레벨씩 올라간다

힙 [5, 9, 11, 14, 18, 19, 21, 33, 17, 27]에 값을 하나 넣는다. 넣을 값과 진행한 단계를 바꾸면 비교하는 두 칸, 교환 횟수, 배열이 바뀐다.

sift up 단계새 값의 위치와 부모 비교
초록으로 채운 원과 칸이 넣은 값의 현재 위치, 초록 테두리가 비교할 부모다. 빨간 굵은 선은 아직 힙 성질을 어긴 부모와 자식 노드 사이이고, 초록 선은 새 값이 올라온 길이다. 원과 칸 아래 작은 수가 인덱스다.

최솟값을 빼면 마지막 값이 루트로 올라와 더 작은 자식 노드와 바꾸며 내려간다

같은 힙에서 루트 5를 꺼낸다. 교환 대상을 고르는 규칙과 진행한 단계를 바꾸면 27이 내려가는 길과 끝난 뒤 힙 성질을 지키는지가 바뀐다.

sift down 단계내려가는 값과 자식 노드 비교
초록으로 채운 원과 칸이 내려가는 값의 현재 위치, 초록 테두리가 비교할 자식 노드다. 빨간 굵은 선과 빨간 원은 힙 성질을 어긴 부모와 자식 노드다. 배열 오른쪽의 점선 칸은 꺼낸 뒤 비게 된 마지막 칸이다.

heappush로 넣은 리스트는 정렬되어 있지 않아도 힙 성질은 지킨다

빈 리스트에 4, 9, 3, 7, 5, 1, 6, 8, 2를 차례로 heappush한다. 넣은 개수를 바꾸면 내부 list, 트리 모양, 이번 삽입의 sift up 교환 횟수가 바뀐다.

heappush 결과내부 list와 트리
위는 내부 list를 레벨 순서로 읽은 트리, 아래는 list 자체다. 초록 원과 칸은 이번에 넣은 값이 sift up을 마친 자리다.